package linkedlist.list_oj;

import java.util.List;

//Definition for singly-linked list.
public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

//合并两个有序链表
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null&&list2 == null) {
            return null;
        }
        ListNode head = new ListNode(0);
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        ListNode cur = head;
        while (cur1 != null&&cur2 != null) {
            if (cur1.val < cur2.val) {
                cur.next = cur1;
                cur1 = cur1.next;
                cur = cur.next;
                continue;
            }
            if (cur1.val > cur2.val) {
                cur.next = cur2;
                cur2 = cur2.next;
                cur = cur.next;
                continue;
            }
            if (cur1.val == cur2.val) {
                cur.next = cur1;
                cur1 = cur1.next;
                cur = cur.next;
                cur.next = cur2;
                cur2 = cur2.next;
                cur = cur.next;
                continue;
            }
        }
        if (cur1 == null) {
            cur.next = cur2;
        }
        if (cur2 == null) {
            cur.next = cur1;
        }
        return head.next;
    }

    //删除链表中所有值为value的元素
    public ListNode removeElements(ListNode head, int val) {
        ListNode cur = head;
        ListNode prev = null; // 标记cur的前一个
        while(null != cur){
            if(val == cur.val){
                if(null == prev){
                    // 删除的是第一个节点
                    head = cur.next;
                }else{
                    // 删除的不是第一个节点
                    prev.next = cur.next;
                }
            }else{
                prev = cur;
            }
            cur = cur.next;
        }
        return head;
    }

    //获取链表倒数第K个节点
    public ListNode FindKthToTail(ListNode head,int k) {
        // 1. front先往后走k步
        ListNode front = head;
        while(0 != k--){
            // 如果front为空，说明k大于链表中节点个数
            if(null == front){
                return null;
            }
            front = front.next;
        }
        // 然后front和back同时往后移动，
        // 当front走到末尾的时候，back刚好是倒数第k个节点
        ListNode back = head;
        while(null != front){
            front = front.next;
            back = back.next;
        }
        return back;
    }

    //获取链表的中间节点
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        // 注意while循环条件
        // null != fast成立：可以保证第一步成功
        // null != fast.next成立：可以保证第二步走成功
        while(null != fast && null != fast.next){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    //反转链表
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        ListNode prev = null;
        ListNode cur = head;
        ListNode tail = head.next;
        while (cur != null) {
            cur.next = prev;
            prev = cur;
            cur = tail;
            if (tail.next == null) {
                cur.next = prev;
                return cur;
            }
            tail = tail.next;
        }
        return null;
    }

    //给定 x, 把一个链表整理成前半部分小于 x, 后半部分大于等于 x 的形式
    public ListNode partition(ListNode pHead, int x) {
        if(pHead == null) {
            return null;
        }
        if(pHead.next == null) {
            return pHead;
        }
        // write code here
        ListNode head = new ListNode(0);
        ListNode prev = head;
        ListNode head2 = new ListNode(0);
        ListNode tail = head2;
        ListNode cur = pHead;
        for(;cur != null;cur = cur.next) {
            if(cur.val < x) {
                prev.next = cur;
                prev = prev.next;
            }else {
                tail.next = cur;
                tail = tail.next;
            }
        }
        tail.next = null;
        prev.next = head2.next;
        return head.next;
    }

    //判定链表是否是回文
    //简单粗暴
    public boolean chkPalindrome1(ListNode A) {
        // write code here
        if (A == null || A.next == null) {
            return true;
        }
        ListNode cur = A;
        ListNode newHead = new ListNode(0);
        ListNode B = newHead;
        for (;cur != null;cur = cur.next) {
            B.next = new ListNode(cur.val);
            B = B.next;
        }
        B = newHead.next;
        ListNode prev = null;
        cur = B;
        while (cur != null) {
            ListNode tail = cur.next;
            cur.next = prev;
            prev = cur;
            cur = tail;
        }
        ListNode head = A;
        while (head != null && prev != null) {
            if (head.val != prev.val) {
                return false;
            }
            head = head.next;
            prev = prev.next;
        }
        if (head == null && prev == null) {
            return true;
        }
        return false;
    }
    //循规蹈矩
    public boolean chkPalindrome2(ListNode A) {
        // write code here
        if (A == null || A.next == null) {
            return true;
        }
        int size = size(A);
        int step = size / 2;
        ListNode B = A;
        for (int i = 0;i < step;i++) {
            B = B.next;
        }
        ListNode prev = null;
        ListNode cur = B;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            if (next == null) {
                B = cur;
                break;
            }
            prev = cur;
            cur = next;
        }
        ListNode head1 = A;
        ListNode head2 = B;
        while (head1 != null && head2 != null) {
            if (head1.val != head2.val) {
                return false;
            }
            head1 = head1.next;
            head2 = head2.next;
        }
        return true;
    }

    //判定链表相交
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        int size1 = size(headA);
        int size2 = size(headB);
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        if (size1 > size2) {
            for (int i = 0;i < size1 - size2;i++) {
                cur1 = cur1.next;
            }
        }else {
            for (int i = 0;i < size2 - size1;i++) {
                cur2 = cur2.next;
            }
        }
        while (cur1 != null && cur2 != null) {
            if (cur1 == cur2) {
                return cur1;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return null;
    }

    //链表长度
    public int size(ListNode head) {
        int size = 0;
        for (ListNode cur = head;cur != null;cur = cur.next) {
            size++;
        }
        return size;
    }

    //判断链表带环
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode cur1 = head;
        ListNode cur2 = head;
        while (cur2 != null) {
            cur1 = cur1.next;
            cur2 = cur2.next;
            if (cur2 == null) {
                return false;
            }
            cur2 = cur2.next;
            if (cur1 == cur2) {
                return true;
            }
        }
        return false;
    }

    //求环的入口点
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode cur1 = head;
        ListNode cur2 = head;
        ListNode cur = null;
        while (cur2 != null) {
            cur1 = cur1.next;
            cur2 = cur2.next;
            if (cur2 == null) {
                return null;
            }
            cur2 = cur2.next;
            if (cur1 == cur2) {
                cur = cur1;
                break;
            }
        }
        if (cur == null) {
            return null;
        }
        ListNode prev = head;
        while (true) {
            if (prev == cur) {
                return prev;
            }
            prev = prev.next;
            cur = cur.next;
        }
    }
}
